package dualpointer;

public class D230829 {
    // 盛水最多的容器
    // 双指针，初始状态指向数组首尾
    // 计算并更新最大容量
    // 然后较短的一边向中间靠
    // 继续计算容量
    // 时间：O(N)
    // 空间：O(1)
    public int maxArea (int[] height) {
        int n = height.length;
        if (n < 2) {
            return 0;
        }
        int res = 0, left = 0, right = n - 1;
        while (left != right) {
            int x = height[left];
            int y = height[right];
            int length = right - left;
            int tmp = Math.min(x, y) * length;
            res = Math.max(res, tmp);
            if (x < y) {
                left++;
            } else {
                right--;
            }
        }
        return res;
    }


    // 最小覆盖子串
    // 检查是否有小于 0 的（T 字符串中的字符，是否已经全部出现）
    boolean check(int[] hash) {
        for (int i = 0; i < hash.length; i++) {
            if (hash[i] < 0)
                return false;
        }
        return true;
    }
    public String minWindow (String S, String T) {
        // 表示子串的 最大长度 - 1
        int cnt = S.length() + 1;

        // 使用数组作为哈希表，用来存储 S 中字符出现的次数
        int[] hash = new int[128];

        // 将 T 中出现的字符，在哈希表中次数进行 -1
        for (int i = 0; i < T.length(); i++) {
            hash[T.charAt(i)] -= 1;
        }
        // 哈希表中为负数的字符，就是组成 T 的字符

        // 滑动窗口 遍历 S 字符串
        int slow = 0, fast = 0;
        // 记录最小子串的下标
        int left = -1, right = -1;

        // 遍历 S 字符串
        for (; fast < S.length(); fast++) {
            char c = S.charAt(fast);
            // 当前字符出现次数 +1
            hash[c]++;

            // 检查 哈希表 中组成 T 的字符是否都出现了。
            while (check(hash)) {
                // 记录 子串 的下标
                // 并且更新子串的最大长度
                if (cnt > fast - slow + 1) {
                    cnt = fast - slow + 1;
                    left = slow;
                    right = fast;
                }
                // 窗口左移，同时哈希表中减少对应字符出现的次数
                hash[S.charAt(slow)]--;
                slow++;
            }
        }
        // 找不到的情况
        if (left == -1) {
            return "";
        }
        return S.substring(left, right + 1);
    }
}
